
// https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/

class Solution
{
    int res = 0;
    int m, n, k;
    vector<vector<int>> used;

public:
    int wardrobeFinishing(int _m, int _n, int cnt)
    {
        m = _m;
        n = _n;
        k = cnt;
        used = vector<vector<int>>(m, vector(n, 0));
        dfs(0, 0);
        return res;
    }

    void dfs(int i, int j)
    {
        used[i][j] = 1;
        ++res;
        if (i + 1 < m && dig(i + 1) + dig(j) <= k && used[i + 1][j] == 0)
            dfs(i + 1, j);
        if (j + 1 < n && dig(i) + dig(j + 1) <= k && used[i][j + 1] == 0)
            dfs(i, j + 1);
    }

    int dig(int x)
    {
        int sum = 0;
        while (x)
        {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
};